#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    int trap(vector<int>& height) {
        stack<int> stk;
        int n = height.size();
        int res = 0;
        for (int i = 0; i < n; i++)
        {
            if (stk.size() == 0) stk.push(i);
            else if (stk.size() && height[stk.top()] > height[i])
            {
                stk.push(i);
            }
            else
            {
                int prev = stk.top();
                stk.pop();
                while (stk.size() && height[stk.top()] <= height[i])
                {
                    res += (height[stk.top()] - height[prev]) * (i - stk.top() - 1);
                    prev = stk.top();
                    stk.pop();
                }
                if (height[prev] == height[i]) stk.push(prev);
                else if (stk.size())
                {
                    res += (height[i] - height[prev]) * (i - stk.top() - 1);
                }
                stk.push(i);
            }
        }
        return res;
    }
};